package com.aurora.leetcode.answer;

import com.aurora.leetcode.util.MyUtils;

import java.util.*;

/**
 * @author : Aurora
 * @date : 2024/5/7 09:59
 * @description 349.两个数组的交集
 * <p>给定两个数组 nums1 和 nums2 ，返回 它们的交集。输出结果中的每个元素一定是 唯一 的。
 * 我们可以 不考虑输出结果的顺序 。</p>
 * <p>exp1</p>
 * <p>输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]</p>
 * <p>exp2</p>
 * <p>示例 2：
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 * 解释：[4,9] 也是可通过的</p>
 */
public class Intersection_349 {
    /**
     * 方法一：使用map计数
     * <p>对于判断元素是否包含也可以使用list.retainAll(Collection collection)方法</p>
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        int size = nums1.length > nums2.length ? nums2.length : nums1.length;
        int[] intersection = new int[size];
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1) {
            map.put(num1, 0);
        }
        int count = 0;
        for (int num2 : nums2) {
            Integer integer = map.get(num2);
            if (integer == null || integer.intValue() != 0) continue;
            else {
                intersection[count++] = num2;
                map.put(num2, 1);
            }
        }
        return Arrays.stream(intersection).limit(count).toArray();


    }

    /**
     * 方法二：排序+双指针
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int size = Math.min(length1, length2);
        int[] intersection = new int[size];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2){
            int num1 = nums1[index1];
            int num2 = nums2[index2];
            if(num1 == num2){
                //去重
                if(index == 0 || num1 != intersection[index-1]){
                    intersection[index++] = num1;
                }
                index1 ++;
                index2 ++;

            } else if(num1 < num2){
                index1 ++;
            }else{
                index2 ++;
            }
        }
        return Arrays.copyOfRange(intersection,0,index);
    }

    public static void main(String[] args) {
        Intersection_349 obj = new Intersection_349();
//        int[] arr1 = new int[]{1,2,2,1};
//        int[] arr2 = new int[]{2,2};
        int[] arr1 = new int[]{4, 9, 5};
        int[] arr2 = new int[]{9, 4, 9, 8, 4};
        //方法一：map计数
//        int[] intersection = obj.intersection(arr1, arr2);
//        MyUtils.printArray(intersection);
        //方法二：排序+双指针
        int[] intersection = obj.intersection2(arr1, arr2);
        MyUtils.printArray(intersection);

    }
}
